/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:DELL
 * Date:2025-07-13
 * Time:12:02
 */
public class Demo2 {
        Map<Character,Set<Character>> edges =new HashMap<>();//邻接表
        Map<Character,Integer> in = new HashMap<>();//统计每个节点的入度
        boolean check;
        public String alienOrder(String[] words) {
            //1.初始化入度哈希表+建图
            for(String s : words){
                for(int i=0;i<s.length();i++){
                    char ch = s.charAt(i);
                    in.put(ch,0);
                }
            }
            int n=words.length;
            for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++){
                    add(words[i],words[j]);
                    if(check == true){
                        return "";
                    }
                }
            }
            //2.拓扑排序
            Queue<Character> q=new LinkedList<>();
            for(char ch : in.keySet()){
                if(in.get(ch)==0){
                    q.add(ch);
                }
            }
            StringBuffer ret = new StringBuffer();
            while(!q.isEmpty()){
                char t=q.poll();
                ret.append(t);
                if(!edges.containsKey(t)){
                    continue;
                }
                for(char ch : edges.get(t)){
                    in.put(ch,in.get(ch)-1);
                    if(in.get(ch)==0){
                        q.add(ch);
                    }
                }
            }
            //5.判断
            for(char ch : in.keySet()){
                if(in.get(ch)!=0){
                    return "";
                }
            }
            return ret.toString();
        }
        public void add(String s1,String s2){
            int n=Math.min(s1.length(),s2.length());
            int i=0;
            for( ;i<n;i++){
                char c1=s1.charAt(i),c2=s2.charAt(i);
                if(c1!=c2){
                    //c1->c2
                    if(!edges.containsKey(c1)) {
                        edges.put(c1,new HashSet<>());
                    }
                    if(!edges.get(c1).contains(c2)){
                        edges.get(c1).add(c2);
                        in.put(c2,in.get(c2)+1);
                    }
                    break;
                }
            }
            if(i==s2.length()&&i<s1.length()){
                check = true;
            }
        }
}
